package list.DeleteList;

import list.ListNode;

/**
 * @ClassName RemoveList
 * @Description TODO
 * @Author lenovo
 * @Date 2023-02-17 14:04
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class RemoveList {

    /**
     * 19. 删除链表的倒数第 N 个结点
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：head = [1,2,3,4,5], n = 2
     * 输出：[1,2,3,5]
     * 示例 2：
     * <p>
     * 输入：head = [1], n = 1
     * 输出：[]
     * 示例 3：
     * <p>
     * 输入：head = [1,2], n = 1
     * 输出：[1]
     */

    public ListNode removeNthFromEnd(ListNode head, int n) {

        if (head == null) {
            return head;
        }

        ListNode pre = reverseList(head);

        ListNode yummy = new ListNode(0);
        ListNode nowListNode = yummy;
        yummy.next = pre;
        for (int i = 1; i < n; i++) {
            yummy = yummy.next;
        }
        yummy.next = yummy.next.next;

        return reverseList(nowListNode.next);
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }


    public ListNode removeNthFromEnd1(ListNode head, int n) {

        if (head == null) return null;

        ListNode fastListNode = new ListNode(0);
        fastListNode.next = head;
        for (int i = 0; i < n; i++) {
            fastListNode = fastListNode.next;
        }

        ListNode slowListNode = new ListNode(0);
        slowListNode.next = head;
        ListNode yummy = slowListNode;
        while (fastListNode.next != null) {
            slowListNode = slowListNode.next;
            fastListNode = fastListNode.next;
        }
        slowListNode.next = slowListNode.next.next;

        return yummy.next;
    }


    public static void main(String[] args) {

        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        ListNode head5 = new ListNode(5);
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;
        RemoveList removeList = new RemoveList();
        System.out.println(removeList.removeNthFromEnd1(head1, 2));
    }

}